package main

import "math/rand"

type Solution struct {
	arr [][2]int
	sum int
}

func Constructor(w []int) Solution {
	var arr [][2]int
	cursor := 0
	for _, wei := range w {
		arr = append(arr, [2]int{cursor, cursor + wei - 1})
		cursor += wei
	}
	return Solution{
		arr: arr,
		sum: arr[len(arr)-1][1],
	}
}

func (this *Solution) PickIndex() int {
	target := rand.Intn(this.sum + 1)
	i := 0
	j := len(this.arr) - 1
	for i <= j {
		mid := (i + j) / 2
		if this.arr[mid][1] <= target {
			i = mid + 1
		} else if this.arr[mid][1] > target {
			j = mid - 1
		}
	}
	if j < 0 {
		return 0
	}
	if this.arr[j][1] == target || j == len(this.arr)-1 {
		return j
	}
	return j + 1
}

func main() {
	solution := Constructor([]int{4, 2})
	for i := 0; i < 10; i++ {
		println(solution.PickIndex())
	}
}
